package comprehensive;

public class Exercises9 {
    // 526、优美的排序
    int ret;
    boolean[] check; // 用于剪枝的，判断上一层是否使用了当前的数据

    public int countArrangement(int n) {
        check = new boolean[n + 1];// 因为是从1开始计数下标的

        dfs(1,n);

        return ret;
    }

    public void dfs(int pos,int n) {
        // 对于pos是从1开始的，我们每次当判断一层之后，递归到下一层才进行比较，所以这里的pos要比正常的n长1
        if(pos == n + 1) {
            // 只要进入到这个函数中，就说明这是一个优美的排序，因为不符合条件的都不会进入到下面的主判断中
            ret++;
            return;
        }

        for(int i = 1;i <= n;i++) {
            // pos 我们要判断的数字，因为pos也是从1开始递增的
            if(check[i] == false && (pos % i == 0 || i % pos == 0)) {
                // 这里不用关心，这个数是否需要放入一个数组中，因为我们需要的知识次数，直接进行判断就可以了
                check[i] = true;
                dfs(pos + 1,n);
                check[i] = false;
            }
        }
    }
}
